package 力扣._00周赛._370周赛.问题2;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    // 拓扑排序
    public int topologicalSort(int n, int[][] edge) {

        Stack<Integer> stack = new Stack<>();
        int[] degree = new int[n];    //入度
        List<Integer> path = new ArrayList<>(n);  //拓扑序列
        //初始化出度
        for (int i = 0; i < n; i++) {
            //计算顶点i的入度
            for (int j = 0; j < n; j++) {
                if (edge[i][j] > 0)
                    degree[i]++;
            }
        }
        //出度为0的顶点入栈
        for (int i = 0; i < n; i++) {
            if (degree[i] == 0)
                stack.push(i);
        }

        while (!stack.isEmpty()) {
            int v = stack.pop();
            path.add(v);
            //更新其他顶点出度
            for (int i = 0; i < n; i++) {
                if (edge[i][v] > 0) {
                    degree[i]--;
                    if (degree[i] == 0)
                        stack.push(i);
                }
            }
        }
        if (path.size() == n)
            return path.get(n - 1);
        else
            return -1;
    }

    public int findChampion(int n, int[][] edges) {
        //DFS，找到拓扑排序，这源点更强，故得找出度为0的点, 有两个入度为0的点也不行
        //是否有两个入度为0
        int[] degree = new int[n];
        for (int[] edge : edges) {
            degree[edge[1]]++;
        }
        int m = -1, c = 0;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 0) {
                m = i;
                c++;
            }
        }
        if (m > 1)
            return -1;
        return m;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = new int[][]{{0, 2}, {1, 3}, {1, 2}};
        int champion = new Solution().findChampion(n, edges);
        System.out.println(champion);
    }
}

